package 回溯;
import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;
/**
 * 不写 不知道 一 写 这个 代码 就发现 
 * 这个 递归 回溯 还是   与 之前写 的 那些  递归回溯 还是 不一样的
 * (与组合 求和 问题  的 递归回溯  的 去黑还是 很大的)
 * 
 * @author I adore you
 *
 */
/**
 * 目前来看 是 ac的 
 * @author I adore you
 *
 */
public class 左程云faceBook原题 {
	static List<List<String>> ans = new ArrayList<>();
	static Deque<String> path = new ArrayDeque<>();
	public static void main(String []args) {
//			System.out.println((char)('A' + 10));
		String s ="12324";
		backTracing(s,0);
		System.out.println(ans);
		System.out.println(ans.size());
		}
	public static void backTracing(String arr ,int index) {
		if(index == arr.length()) {
			ans.add(new ArrayList<>(path));
			return ;
		}
		if(arr.charAt(index) == '0') {
			return ;
		}
		if(arr.charAt(index) == '1') {
			path.addLast("A");
			backTracing(arr,index + 1);
			path.removeLast();
			if(index + 1 < arr.length()) {
//				'A' + Integer.parseInt(arr.substring(index, index+2))
				path.add((char)(Integer.parseInt(arr.substring(index, index + 2)) - 1 +'A') + "");
				backTracing(arr,index + 2);
//				path.removeLast();
//				  这个 撤销的 操作   感觉  不要 你感觉 还是 要 具体 去分析的 
				path.removeLast();
			}
		}
		else if(arr.charAt(index) == '2') {
			path.add("B");
			backTracing(arr,index + 1);
			path.removeLast();
			if(index + 1 < arr.length() && '0'<=arr.charAt(index + 1) && arr.charAt(index + 1)<='6') {
				path.add((char)(Integer.parseInt(arr.substring(index,index + 2))- 1 + 'A') + "");
				backTracing(arr,index + 2);
				path.removeLast();
			}
		}
		else {
			// 这种情况只能 单独开头
			path.addLast((char)(arr.charAt(index) - '0' + 'A' - 1) + "");
			backTracing(arr,index + 1);
			// 回溯一下!
			path.removeLast();
		}
	}
}
